class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length() == 1) return s;
        if(s.length() % 2 == 0) s = s + '#';
        int i = 0, j;
        int max = 1;
        int idx;
        for(i = 0; i < s.length() - 1; ++i) {
            for(j = 1; (i - j) >= 0 && (i + j) < s.length(); ++j) {
                if(s[i - j] != s[i + j]) break;
            }
            if((j - 1) * 2 + 1 > max) {
                max = (j - 1) * 2 + 1;
                idx = i;
            }
            for(j = 1; (i + 1 - j) >= 0 && (i + j) < s.length(); ++j) {
                if(s[i + 1 - j] != s[i + j]) break;
            }
            if((j - 1) * 2 > max) {
                max = (j - 1) * 2;
                idx = i;
            }
        }
        if(max == 1) return s.substr(0, 1);
        if(max % 2 != 0) {
            return s.substr(idx - max / 2, max);
        } else {
            return s.substr(idx + 1 - max / 2, max);
        }
    }
};
